The present invention generally relates to accessing data and more specifically to retrieving elements of documents using step queries generated from a query.
Many languages, such as Extensible Markup Language (XML), define rules that are used for structuring data. An XML document is created using the rules to structure data and includes two parts: the marked up document and the document schema. The marked up part of the document encodes a description of the document's storage layout and logical structure. The schema part specifies constraints that define XML document structures.
XML documents are made up of storage units called elements, which may be nested to form a hierarchical structure. An element may contain either parsed or unparsed data. Parsed data is made up of characters, some of which form character data, and some of which form the markup; unparsed data is data in its native format. Also, XML elements may have associated attributes, which may be referred to as name-value pairs. Elements and attributes are described in XML schema where the schema includes, for each element that may occur in the document, a name, the type, the set of attributes, and the set of allowable constituent elements. The relations are represented in a graph with one vertex for each element name, and one edge from an element to each possible constituent.
In managing XML documents, retrieving elements in the documents for reading or reformatting is often necessary. Accordingly, several query languages have been proposed for searching for and retrieving elements in the XML documents. For example, XQuery, a language derived from an XML query language Quilt and borrowing features from other languages, including XPath, is used for accessing elements in an XML document. XQuery accesses an element using a feature from XPath called an XPath location path expression, which specifies a pattern of elements within the XML document. For example, a query may be of the form A/B/C/D, and is interpreted to specify a pattern of the elements A, B, C, and D within the structure of the XML document. In order to find the desired element D, a system traces the hierarchy of the XML document. The system finds in order, all instances of the element A, all instances of the element B related to element A, all instances of the element C related to the A/B group, and all instances of the element D related to the A/B/C group. Thus, the system processes the XQuery command sequentially, starting from the first element and then to each subsequent element. This method of accessing elements in an XML document becomes time consuming and requires extensive computing power, especially when an element is deeply nested in a hierarchical XML document or a query includes a long path of elements.